﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Sort
{
    class MergeSort
    {
        public static void Sort(int[] arr, int beg, int end)
        {
            Sort_(arr, beg, end);
        }

        static void Sort_(int[] arr, int beg, int end)
        {
            if (end <= beg)
                return;

            if(end - beg == 1)
            {
                if (arr[beg] > arr[beg + 1])
                    lib.Swap<int>(arr, beg, beg + 1);
                return;
            }

            int mid = beg + (end - beg) / 2;
            Sort_(arr, beg, mid);
            Sort_(arr, mid + 1, end);
            Merge(arr, beg, mid+1, end);
        }

        public static void Merge(int[] arr, int leftBegin, int rightBegin, int end)
        {
            if (end - rightBegin < 0)
                return;

            int current = leftBegin;
            int moveNum = 0;
            for (int i = rightBegin; i <= end; i++)
            {
                for (; current < rightBegin + moveNum; current++)
                {
                    if (i < arr.Length && arr[current] > arr[i])
                    {
                        int temp = arr[i];
                        for(int idx = i; idx > current; idx--)
                        {
                            arr[idx] = arr[idx - 1];
                        }
                        arr[current] = temp;
                        current++;
                        moveNum++;
                        break;
                    }
                }
            }
        }
    }
}
